package edu.cuit.avatar.recursive;

/**
 * @author <a href="mailto:1020zhaodan@163.com">Adan</a>
 * @version 1.0
 * @date 2025/7/14 9:14
 */
public class RecursivePalindrome {
    public static void main(String[] args) {
        System.out.println(isPalindrome("11111"));
        System.out.println(isPalindrome("11112"));
    }

    /**
     * 使用递归的思路判断一个字符串是否为回文字符串
     * 1.检查字符串第一个字符和最后一个字符是否相等
     * 2.忽略两端字符之后检查子串其余部分是否为回文串
     */
    public static boolean isPalindrome(String str) {
//        if(str.length() <= 1)
//            return true;
//        else if(str.charAt(0) != str.charAt(str.length()-1))
//            return false;
//        //substring每次会产生一个新的字符串,因此不够高效
//        else return isPalindrome(str.substring(1, str.length()-1));
        return isPalindrome(str, 0, str.length() - 1);
    }

    /**
     * 递归辅助方法:避免创建新的字符串，使用low和high下标表明子串的范围
     * @param str 字符串
     * @param low 低位索引
     * @param high 高位索引
     * @return 回文串：true
     */
    private static boolean isPalindrome(String str, int low, int high) {
        if(high <= low)
            return true; //基础情况
        else if (str.charAt(low) != str.charAt(high))
            return false; //基础情况
        return isPalindrome(str, low + 1, high - 1);
    }
}
